package main.剑指OfferⅡ;

import java.util.*;

public class Day5_Day8 {
    public static void main(String[] args) {
        System.out.println("**************************Day5**************************");
        System.out.println("剑指OfferⅡ014.字符串中的变位词");
        System.out.println("剑指OfferⅡ015.字符串中的所有变位词");
        System.out.println("剑指OfferⅡ016.不含重复字符的最长子字符串");
        System.out.println("**************************Day6**************************");
        System.out.println("剑指OfferⅡ017.含有所有字符的最短字符串");
        System.out.println("剑指OfferⅡ018.有效的回文");
        System.out.println("剑指OfferⅡ019.最多删除一个字符得到回文");
        System.out.println("剑指OfferⅡ020.回文子字符串的个数");
        System.out.println("**************************Day7**************************");
        System.out.println("剑指OfferⅡ021.删除链表的倒数第n个结点");
        System.out.println("剑指OfferⅡ022.链表中环的入口节点");
        System.out.println("剑指OfferⅡ023.两个链表的第一个重合节点");
        System.out.println("**************************Day8**************************");
        System.out.println("剑指OfferⅡ024.反转链表");
        System.out.println("剑指OfferⅡ025.链表中的两数相加");
        System.out.println("剑指OfferⅡ026.重排链表");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Offer14{
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()) return false;
        int[] count1=new int[26],count2=new int[26];
        char[] str1=s1.toCharArray(),str2=s2.toCharArray();
        for (char c:str1){//统计s1各个字符个数
            ++count1[c-'a'];
        }
        int left=0,right=0;//指定固定大小窗口
        for (right=0;right< str1.length;right++){
            ++count2[str2[right]-'a'];
        }
        if (Arrays.equals(count1,count2)) return true;
        for (;right< str2.length;right++){
            --count2[str2[left]-'a'];//左缩
            left++;
            ++count2[str2[right]-'a'];//右扩
            if (Arrays.equals(count1,count2)) return true;
        }
        return false;
    }
}

class Offer15{
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list=new ArrayList<>();
        if (s.length()<p.length()) return list;
        char[] str1=s.toCharArray(),str2=p.toCharArray();
        int[] count1=new int[26],count2=new int[26];
        for (int i=0;i< str2.length;i++){
            ++count1[str1[i]-'a'];
            ++count2[str2[i]-'a'];
        }
        if (Arrays.equals(count1,count2)) list.add(0);
        int left=0,right= str2.length;
        for (;right< str1.length;right++){
            --count1[str1[left]-'a'];
            left++;
            ++count1[str1[right]-'a'];
            if (Arrays.equals(count1,count2)) list.add(left);
        }
        return list;
    }
}

class Offer16{
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set=new HashSet<>();
        char[] str=s.toCharArray();
        int max=0,left=0,right=0;
        while (right<s.length()){
            if (set.isEmpty()||!set.contains(str[right])) set.add(str[right]);
            else {
                while (left<right&&str[left]!=str[right]) {//移除重复
                    set.remove(str[left]);
                    left++;
                }
                set.remove(str[right]);
                left++;
                set.add(str[right]);//加入新扩字符
            }
            right++;
            max=Math.max(set.size(),max);
        }
        return max;
    }
}

class Offer17{
    public boolean process(int[] curCount,int[] targetCount){
        for (int i=0;i< targetCount.length;i++){
            if (targetCount[i]!=0&&curCount[i]<targetCount[i]) return false;//目标字符数不足
        }
        return true;
    }
    public String minWindow(String s, String t) {
        int left=0,right=0,start=-1,minLength=Integer.MAX_VALUE;
        if (t.length()>s.length()) return "";
        int[] targetCount=new int[150],curCount=new int[150];
        char[] str=s.toCharArray();
        for (char c:t.toCharArray()) targetCount[c]++;
        while (right< str.length){
            curCount[str[right]]++;//右扩
            while (process(curCount,targetCount)&&left<=right){//左缩
                if (right-left+1<minLength){//满足更新
                    start=left;
                    minLength=right-left+1;
                }
                curCount[str[left]]--;
                left++;
            }
            right++;
        }
        if (start==-1) return "";
        else return s.substring(start,start+minLength);
    }
}

class Offer18{
    public boolean isPalindrome(String s) {
        StringBuffer stringBuffer=new StringBuffer();
        char[] chars=s.toCharArray();
        for (char c: chars){
            if ((c>='0'&&c<='9')||((c>='a'&&c<='z')||(c>='A'&&c<='Z'))) stringBuffer.append(c);
        }
        char[] str=stringBuffer.toString().toCharArray();
        int left=0,right=str.length-1;
        while (left<right){
            if (str[left]>='0'&&str[left]<='9'&&str[left]!=str[right]) return false;//数字
            else if (!(str[left]>='0'&&str[left]<='9')&&(str[left]!=str[right])&&(Math.abs(str[right]-str[left])!=32))return false;
            left++;
            right--;
        }
        return true;
    }
}

class Offer19{
    public boolean process(char[] str,int low,int high){
        while (low<=high){
            if (str[low]!=str[high]) return false;
            low++;
            high--;
        }
        return true;
    }
    public boolean validPalindrome(String s) {
        char[] str=s.toCharArray();
        int low=0,high= str.length-1;
        while (low<=high){
            if (process(str,low,high)) return true;
            if (str[low]==str[high]){//两边相等
                low++;
                high--;
            }else {//两边不等
                if (process(str,low+1,high)) return true;
                else if (process(str,low,high-1)) return true;
                else return false;
            }
        }
        return false;
    }
}

class Offer20{
    public int countSubstrings(String s) {
        char[] str=s.toCharArray();
        boolean[][] dp=new boolean[str.length][str.length];
        int count=0;
        for (int i=str.length-1;i>=0;i--){
            for (int j=i;j<str.length;j++){
                if (i==j) dp[i][j]=true;
                else if (i+1==j&&str[i]==str[j]) dp[i][j]=true;
                else if (j-i>1){
                    if (str[i]==str[j]&&dp[i+1][j-1]) dp[i][j]=true;
                }
                if (dp[i][j]) count++;
            }
        }
        return count;
    }
}

class Offer21{
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode vir=new ListNode(0),temp=head,pre=head;
        vir.next=head;
        int count=0;
        while (temp!=null){
            temp=temp.next;
            count++;
        }
        temp=vir;
        for (int i=0;i<n ;i++) pre=pre.next;
        while (pre!=null){
            temp=temp.next;
            pre=pre.next;
        }
        temp.next=temp.next.next;
        return vir.next;
    }
}

class Offer22{
    public ListNode detectCycle(ListNode head) {
        if (head==null) return null;
        ListNode fast=head,slow=head;
        do {
            fast=fast.next.next;
            slow=slow.next;
        }while (fast!=slow);
        fast=head;
        while (fast!=slow){
            fast= fast.next;
            slow=slow.next;
        }
        return fast;
    }
}

class Offer23{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA=headA,tempB=headB;
        while (tempA!=null&&tempB!=null){
            tempA=tempA.next;
            tempB=tempB.next;
        }
        if (tempA==null){
            tempA=headB;
            while (tempB!=null){
                tempA=tempA.next;
                tempB=tempB.next;
            }
            tempB=headA;
        }else {
            tempB=headA;
            while (tempA!=null){
                tempA=tempA.next;
                tempB=tempB.next;
            }
            tempA=headB;
        }
        while (tempA!=tempB){
            tempA=tempA.next;
            tempB=tempB.next;
        }
        return tempA;
    }
}

class Offer24{
    public ListNode reverseList(ListNode head) {
        ListNode vir=new ListNode(0),temp=null;
        while (head!=null){
            ListNode curNode=new ListNode(head.val);
            curNode.next=temp;
            vir.next=curNode;
            temp=curNode;
            head=head.next;
        }
        return vir.next;
    }
}

class Offer25{
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuffer num1=new StringBuffer(),num2=new StringBuffer();
        ListNode temp1=l1,temp2=l2,vir=new ListNode(0),last=null;
        while (temp1!=null){
            num1.append(temp1.val);
            temp1=temp1.next;
        }
        while (temp2!=null){
            num2.append(temp2.val);
            temp2=temp2.next;
        }
        char[] str1=num1.toString().toCharArray(),str2=num2.toString().toCharArray();
        int power=0,i=str1.length-1,j=str2.length-1;
        while (i>=0&&j>=0){
            int sum=(str1[i]-'0')+(str2[j]-'0')+power;//相加并进位
            power=sum/10;//本位进位
            ListNode curNode=new ListNode(sum%10);
            curNode.next=last;//头插
            vir.next=curNode;
            last=curNode;
            i--;
            j--;
        }
        while (i>=0){
            int sum=(str1[i]-'0')+power;
            power=sum/10;
            ListNode curNode=new ListNode(sum%10);
            curNode.next=last;
            vir.next=curNode;
            last=curNode;
            i--;
        }
        while (j>=0){
            int sum=(str2[j]-'0')+power;
            power=sum/10;
            ListNode curNode=new ListNode(sum%10);
            curNode.next=last;
            vir.next=curNode;
            last=curNode;
            j--;
        }
        if (power!=0){
            ListNode curNode=new ListNode(power);
            curNode.next=last;
            vir.next=curNode;
            last=curNode;
        }
        return vir.next;
    }
}

class Offer26{
    public void reorderList(ListNode head) {
        List<ListNode> list=new ArrayList<>();
        ListNode temp=head;
        while (temp!=null){
            list.add(temp);
            temp=temp.next;
        }
        List<ListNode> reverseList=new ArrayList<>(list);
        Collections.reverse(reverseList);
        int count=1,index=1,reverseIndex=0;
        temp=head;
        while (count<list.size()){
            temp.next= reverseList.get(reverseIndex);
            count++;
            reverseIndex++;
            temp=temp.next;
            temp.next=list.get(index);
            count++;
            index++;
            temp=temp.next;
        }
        temp.next=null;
    }
}